package com.future.offer;

/**
 * Description: 剑指 Offer II 112. 最长递增路径
 * 输入：matrix = [[9,9,4],[6,6,8],[2,1,1]]
 * 输出：4
 * 解释：最长递增路径为 [1, 2, 6, 9]。
 *
 * @author weiruibai.vendor
 * Date: 2023/1/18 15:52
 */
public class Solution_112 {

    private static Solution_112 instance = new Solution_112();

    public static void main(String[] args) {
        int[][] matrix = {{9, 9, 4}, {6, 6, 8}, {2, 1, 1}};

        matrix = new int[][]{{7, 8, 9}, {9, 7, 6}, {7, 2, 3}};
        System.out.println(instance.longestIncreasingPath(matrix));
        System.out.println(instance.longestIncreasingPath_v2(matrix));
        System.out.println(instance.longestIncreasingPath_dp(matrix));
    }

    public int longestIncreasingPath_dp(int[][] matrix) {
        int N = matrix.length;
        int M = matrix[0].length;
        int ans = 0;
        int[][] dp = new int[N][M];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                int res = calcLongestIncreasingPath_dp(i, j, matrix, dp);
                ans = Math.max(res, ans);
            }
        }
        return ans;
    }


    private int calcLongestIncreasingPath_dp(int i, int j, int[][] matrix, int[][] dp) {
        if (i < 0 || i >= matrix.length || j < 0 || j >= matrix[0].length) {
            return 0;
        }
        if (dp[i][j] != 0) {
            return dp[i][j];
        }
        int val = matrix[i][j];
        // 上
        int res1 = 0;
        if (i - 1 >= 0 && i - 1 < matrix.length && val < matrix[i - 1][j]) {
            res1 = calcLongestIncreasingPath_dp(i - 1, j, matrix, dp);
        }
        // 下
        int res2 = 0;
        if (i + 1 >= 0 && i + 1 < matrix.length && val < matrix[i + 1][j]) {
            res2 = calcLongestIncreasingPath_dp(i + 1, j, matrix, dp);
        }
        // 左
        int res3 = 0;
        if (j - 1 >= 0 && j - 1 < matrix[0].length && val < matrix[i][j - 1]) {
            res3 = calcLongestIncreasingPath_dp(i, j - 1, matrix, dp);
        }
        // 右
        int res4 = 0;
        if (j + 1 >= 0 && j + 1 < matrix[0].length && val < matrix[i][j + 1]) {
            res4 = calcLongestIncreasingPath_dp(i, j + 1, matrix, dp);
        }
        int res = Math.max(Math.max(res1, res2), Math.max(res3, res4)) + 1;
        dp[i][j] = res;
        return res;
    }

    /**
     * @param matrix
     * @return
     */
    public int longestIncreasingPath_v2(int[][] matrix) {
        int N = matrix.length;
        int M = matrix[0].length;
        int ans = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                int res = calcLongestIncreasingPath_v2(i, j, matrix);
                ans = Math.max(res, ans);
            }
        }
        return ans;
    }

    private int calcLongestIncreasingPath_v2(int i, int j, int[][] matrix) {
        if (i < 0 || i >= matrix.length || j < 0 || j >= matrix[0].length) {
            return 0;
        }
        int val = matrix[i][j];
        // 上
        int res1 = 0;
        if (i - 1 >= 0 && i - 1 < matrix.length && val < matrix[i - 1][j]) {
            res1 = calcLongestIncreasingPath_v2(i - 1, j, matrix);
        }
        // 下
        int res2 = 0;
        if (i + 1 >= 0 && i + 1 < matrix.length && val < matrix[i + 1][j]) {
            res2 = calcLongestIncreasingPath_v2(i + 1, j, matrix);
        }
        // 左
        int res3 = 0;
        if (j - 1 >= 0 && j - 1 < matrix[0].length && val < matrix[i][j - 1]) {
            res3 = calcLongestIncreasingPath_v2(i, j - 1, matrix);
        }
        // 右
        int res4 = 0;
        if (j + 1 >= 0 && j + 1 < matrix[0].length && val < matrix[i][j + 1]) {
            res4 = calcLongestIncreasingPath_v2(i, j + 1, matrix);
        }
        return Math.max(Math.max(res1, res2), Math.max(res3, res4)) + 1;
    }

    /**
     * 超时
     *
     * @param matrix
     * @return
     */
    public int longestIncreasingPath(int[][] matrix) {
        int N = matrix.length;
        int M = matrix[0].length;
        int ans = 0;
        for (int i = 0; i < N; i++) {
            boolean[][] visited;
            for (int j = 0; j < M; j++) {
                visited = new boolean[N][M];
                visited[i][j] = true;
                // 上
                int res1 = calcLongestIncreasingPath(matrix[i][j], i - 1, j, matrix, visited);
                // 下
                int res2 = calcLongestIncreasingPath(matrix[i][j], i + 1, j, matrix, visited);
                // 左
                int res3 = calcLongestIncreasingPath(matrix[i][j], i, j - 1, matrix, visited);
                // 右
                int res4 = calcLongestIncreasingPath(matrix[i][j], i, j + 1, matrix, visited);
                int res5 = Math.max(Math.max(res1, res2), Math.max(res3, res4)) + 1;
                ans = Math.max(res5, ans);
            }
        }
        return ans;
    }

    private int calcLongestIncreasingPath(int preValue, int i, int j, int[][] matrix, boolean[][] visited) {
        if (i < 0 || i >= matrix.length || j < 0 || j >= matrix[0].length || visited[i][j] || preValue >= matrix[i][j]) {
            return 0;
        }
        int curVal = matrix[i][j];
        visited[i][j] = true;
        // 上
        int res1 = calcLongestIncreasingPath(curVal, i - 1, j, matrix, visited);
        // 下
        int res2 = calcLongestIncreasingPath(curVal, i + 1, j, matrix, visited);
        // 左
        int res3 = calcLongestIncreasingPath(curVal, i, j - 1, matrix, visited);
        // 右
        int res4 = calcLongestIncreasingPath(curVal, i, j + 1, matrix, visited);
        visited[i][j] = false;
        return Math.max(Math.max(res1, res2), Math.max(res3, res4)) + 1;
    }
}
